/**
 * 堆（最大堆、最小堆）
 * 
 * @author shuyuan.dai 2021-02-04
 */
class Dump {
    constructor(bigEnd = false) {
        this.bigEnd = bigEnd;
        this.store = [];
    }

    satisfy(father, child) {
        return this.bigEnd? father >= child: child >= father;
    }

    swap(i, j) {
        let temp = this.store[i];
        this.store[i] = this.store[j];
        this.store[j] = temp;
    }

    get length() {
        return this.store.length;
    }

    get peek() {
        return this.store.length > 0? this.store[0]: null;
    }

    isEmpty() {
        return this.store.length == 0;
    }

    sifUp(i) {
        while(i > 0) {
            let parent = (i - 1) >> 1;
            if(!this.satisfy(this.store[parent], this.store[i])) {
                this.swap(i, parent);
            }
            i = parent;
        }
    }

    sifDown(i) {
        if(i >= this.store.length) {
            return;
        }

        let parent = (i - 1) >> 1;
        if(parent >= 0 && !this.satisfy(this.store[parent], this.store[i])) {
            this.sifUp(i);
        }

        let rchild = 2 * (i + 1);

        if(rchild >= this.store.length) {
            this.sifDown(rchild - 1);
            return;
        }

        if(this.satisfy(this.store[i], this.store[rchild - 1]) && this.satisfy(this.store[i], this.store[rchild])) {
            return;
        }

        let child = this.satisfy(this.store[rchild - 1], this.store[rchild])? rchild - 1: rchild;
        this.swap(i, child);
        this.sifDown(child);
    }

    add(e) {
        let index = this.store.length;
        this.store[index] = e;
        this.sifUp(index);
    }

    poll() {
        let result = this.store[0];
        this.store[0] = this.store[this.store.length - 1];
        this.store.length--;
        this.sifDown(0);
        return result;
    }

    remove(e) {
        let index = -1;
        for(let i=0; i < this.store.length; ++i) {
            if(this.store[i] == e) {
                index = i;
                break;
            }
        }

        if(index < 0) return;
        this.store[index] = this.store[this.store.length - 1];
        this.store.length--;
        this.sifDown(index);
    }
}

exports.Dump = Dump;